package Java集合;

import org.junit.Test;
import java.util.*;

/*
    Set接口概述
         Set接口是Collection的子接口,set接口没有提供额外的方法
         Set集合不允许包含相同的元素,如果试把两个相同的元素加入同一个Set集合中,则添加操作失败
         Set判断两个对象是否相同不是使用 == 运算符,而是根据equals()方法
         JDK API中Set接口的实现类常用的有:
            HashSet:作为Set接口的主要实现类,线程不安全的,可存储Null值
                LinkedHashSet:(HashSet的子类)遍历其内部数据时,可以按照添加的顺序遍历
            TreeSet:可以按照添加对象的指定属性,进行排序

    Set实现类之一:HashSet
         HashSet是 Set接口的典型实现,大多数时候使用 Set集合时都使用这个实现类
         HashSet按 Hash算法来存储集合中的元素,因此具有很好的存取、查找、删除性能
            HashSet具有以下特点
                  不能保证元素的排列顺序
                  HashSet不是线程安全的
                  集合元素可以是Null
         HashSet集合判断两个元素相等的标准:两个对象通过 hashCode()方法比较相等,并且两个对象的 equals()方法返回值也相等
         对于存放在Set容器中的对象,对应的类一定要重写equals()和hashCode(Object obj)方法,以实现对象相等规则,即:"相等的对象必须具有相等的散列码(哈希值)"

   向HashSet中添加元素的过程
         当向 HashSet集合中存入一个元素时,HashSet会调用该对象的 hashCode()方法来得到该对象的 hashCode值,然后根据 hashCode值
          通过某种散列函数决定该对象在 HashSet底层数组中的存储位置(这个散列函数会与底层数组的长度相计算得到在数组中的下标,，并且这种
          散列函数计算还尽可能保证能均匀存储元素,越是散列分布,该散列函数设计的越好)
         如果两个元素的hashCode()值相等,会再继续调用equals方法,如果equals方法结果为true,添加失败,如果为false,那么会保存该元素,
          但是该数组的位置已经有元素了,那么会通过链表的方式继续链接
         如果两个元素的 equals()方法返回 true,但它们的 hashCode()返回值不相等,hashSet将会把它们存储在不同的位置,但依然可以添加成功

  重写 hashCode()方法的基本原则(Object中的hashCode()可以看成是生成一个随机的值,如果不重写hashCode()方法,那么放入两个相同的对象时,哈希值必定不同,便会存放在底层数组中的不同位置,便会呈现出可以放入相同的元素)
          在程序运行时,同一个对象多次调用 hashCode()方法应该返回相同的值
          当两个对象的 equals()方法比较返回 true时,这两个对象的 hashCode()方法的返回值也应相等
          对象中用作 equals()方法比较的 Field,都应该用来计算 hashCode值

  重写 equals()方法的基本原则
         当一个类有自己特有的"逻辑相等"概念,当改写equals()的时候,总是要改写hashCode(),
           根据一个类的equals方法(改写后),两个截然不同的实例有可能在逻辑上是相等的,但是,
           根据Object.hashCode()方法,它们仅仅是两个对象
         复写equals()方法的时候一般都需要同时复写hashCode()方法,通常参与计算hashCode的
          对象的属性也应该参与到equals()中进行计算

  Set实现类之二:LinkedHashSet
         LinkedHashSet是 HashSet的子类
         LinkedHashSet根据元素的 hashCode值来决定元素的存储位置,但它同时使用双向链表维护元素的次序,这使得元素看起来是以插入顺序保存的
         LinkedHashSet插入性能略低于 HashSet,但在迭代访问 Set里的全部元素时有很好的性能
         LinkedHashSet不允许集合元素重复

  Set实现类之三:TreeSet
         TreeSet是 SortedSet接口的实现类,TreeSet可以确保集合元素处于排序状态
         TreeSet底层使用红黑树结构存储数据,有序,查询速度比List快
         新增的方法(了解即可):
            Comparator comparator()
            Object first()
            Object last()
            Object lower(Object e)
            Object higher(Object e)
            SortedSet subSet(fromElement, toElement)
            SortedSet headSet(toElement)
            SortedSet tailSet(fromElement)
         TreeSet两种排序方法:自然排序和定制排序,默认情况下,TreeSet采用自然排序

     排 序 --> 自然排序
         TreeSet会调用集合元素的 compareTo(Object obj)方法来比较元素之间的大小关系,然后将集合元素按升序(默认情况)排列
         如果试图把一个对象添加到 TreeSet时,则该对象的类必须实现 Comparable接口
         实现 Comparable的类必须实现 compareTo(Object obj)方法,两个对象即通过 compareTo(Object obj)方法的返回值来比较大小
         Comparable的典型实现
              BigDecimal、BigInteger以及所有的数值型对应的包装类,按它们对应的数值大小进行比较
              Character:按字符的 unicode值来进行比较
              Boolean:true 对应的包装类实例大于 false对应的包装类实例
              String:按字符串中字符的 unicode值进行比较
              Date、Time:后边的时间、日期比前面的时间、日期大
        向 TreeSet中添加元素时,只有第一个元素无须比较compareTo()方法,后面添加的所有元素都会调用compareTo()方法进行比较
        因为只有相同类的两个实例才会比较大小,所以向 TreeSet中添加的应该是同一个类的对象
        对于 TreeSet集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过 compareTo(Object obj)方法比较返回值
        当需要把一个对象放入 TreeSet中,重写该对象对应的 equals()方法时,应保证该方法与 compareTo(Object obj)方法有一致的结果,
         如果两个对象通过 equals()方法比较返回 true,则通过 compareTo(Object obj)方法比较应返回0,否则,会难以理解

     排 序 --> 定制排序
        TreeSet的自然排序要求元素所属的类实现Comparable接口,如果元素所属的类没有实现Comparable接口,或不希望按照升序(默认情况)
         的方式排列元素或希望按照其它属性大小进行排序,则考虑使用定制排序,定制排序通过Comparator接口来实现,需要重写compare(T o1,T o2)方法
        利用int compare(T o1,T o2)方法,比较o1和o2的大小,如果方法返回正整数,则表示o1大于o2,如果返回0,表示相等,返回负整数,表示o1小于o2
        要实现定制排序,需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器
        仍然只能向TreeSet中添加类型相同的对象,否则发生ClassCastException异常
        使用定制排序判断两个元素相等的标准是:通过Comparator比较两个元素返回了0
 */
public class SetTest05 {

    @Test
    public void test1(){
        /*
            无序性(无序性不等于随机性):以HashSet为例,存储的数据在底层数组并非按照数组索引的顺序添加,而是根据数据的哈希值决定的
            不可重复性:保证添加的元素按照equals()判断时,不能返回true,即:相同的元素只能添加一个
         */
        Set set = new HashSet();
        set.add(456);
        set.add(123);
        set.add("AA");
        set.add("CC");
        set.add(new Person("Tom",12));
        set.add(new Person("Tom",12));
        set.add(129);

        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

    @Test
    public void test2(){
        HashSet set = new LinkedHashSet();
        set.add(456);
        set.add(123);
        set.add("AA");
        set.add("CC");
        set.add(new Person("Tom",12));
        set.add(new Person("Tom",12));
        set.add(129);

        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

    /*
        向TreeSet中添加的数据,要求是相同类的对象,否则运行报错
     */
    @Test
    public void test3(){
        TreeSet set = new TreeSet();

        //失败:不能添加不同类的对象
//        set.add(123);
//        set.add(456);
//        set.add("AA");
//        set.add(new Person("Tom",12));

        set.add(-1);
        set.add(34);
        set.add(12);
        set.add(98);
        set.add(0);
        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

    /*
        自然排序:比较两个对象是否相同的标准为compareTo()返回0,不再是equals()
     */
    @Test
    public void test4(){
        Set set = new TreeSet();
        set.add(new Person("Tom",12));
        set.add(new Person("Jerry",13));
        set.add(new Person("Kitty",14));
        set.add(new Person("Ming",12));
        set.add(new Person("Mike",11));
        set.add(new Person("Mike",56));

        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

    /*
        定制排序:比较两个对象是否相同的标准为compare()返回0,不再是equals()
     */
    @Test
    public void test5(){
        //按照年龄从小到大排序(年龄一样的舍弃)
        Comparator com = new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Person && o2 instanceof Person){
                    Person p1 = (Person) o1;
                    Person p2 = (Person) o2;
                    return Integer.compare(p1.getAge(),p2.getAge());
                }
                throw new RuntimeException("类型不匹配!");
            }
        };

        SortedSet set = new TreeSet(com);
        set.add(new Person("Tom",12));
        set.add(new Person("Jerry",13));
        set.add(new Person("Kitty",14));
        set.add(new Person("Ming",12));
        set.add(new Person("Mike",11));
        set.add(new Person("Mike",56));

        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

    /*
       List转Set去重示例
     */
    @Test
    public void test6() {
        List list = new ArrayList();
        list.add(new Integer(1));
        list.add(new Integer(2));
        list.add(new Integer(2));
        list.add(new Integer(4));
        list.add(new Integer(4));
        List list2 = duplicateList(list);
        for (Object integer : list2) {
            System.out.println(integer);
        }

        //或
        Set set = new HashSet(list);
    }

    public static List duplicateList(List list) {
        HashSet set = new HashSet();
        set.addAll(list);
        return new ArrayList(set);
    }

    /*
        经典面试题
     */
    @Test
    public void test7() {
//        HashSet set = new HashSet();
//        Person p1 = new Person(1001, "AA");  //已经重写了equals()和hashCode()
//        Person p2 = new Person(1002, "BB");
//        set.add(p1);
//        set.add(p2);
//        p1.name = "CC";
//        set.remove(p1);
//        System.out.println(set);
//        set.add(new Person(1001, "CC"));
//        System.out.println(set);
//        set.add(new Person(1001, "AA"));
//        System.out.println(set);
    }
}
